// 300.[dp动态规划二分/例子] 最长递增子序列
// https://leetcode-cn.com/problems/longest-increasing-subsequence/
// 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
// 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
// 例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
// 输入：nums = [10,9,2,5,3,7,101,18]
// 输出：4
// 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
// 输入：nums = [0,1,0,3,2,3]
// 输出：4
// 输入：nums = [7,7,7,7,7,7,7]
// 输出：1
// 提示：1 <= nums.length <= 2500, -104 <= nums[i] <= 104
// 进阶：你能将算法的时间复杂度降低到O(n log(n)) 吗

// dp动态规划 时间 O(n^2)
// 定义 dp[i] 为考虑前 i 个元素，以第 i 个数字结尾的最长上升子序列的长度，注意
// nums[i] 必须被选取。 我们从小到大计算 dp 数组的值，在计算 dp[i]
// 之前，我们已经计算出 dp[0…i−1] 的值，则状态转移方程为：
// dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]
// 即考虑往 dp[0…i−1] 中最长的上升子序列后面再加一个 nums[i]。

#include <bits/stdc++.h>
using namespace std;

#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#define FRE(x)                    \
  freopen("d:/oj/" #x ".in", "r", \
          stdin)  //,freopen("d:/oj/"#x".out","w",stdout)
#define FREC fclose(stdin), fclose(stdout);
#else
#define PF(...)
#define FRE(x)
#define FREC
#endif

class Solution_dp {
 public:
  int lengthOfLIS(vector<int>& nums) {
    int n = (int)nums.size();
    if (n == 0) {
      return 0;
    }
    vector<int> dp(n, 0);
    for (int i = 0; i < n; ++i) {
      dp[i] = 1;
      for (int j = 0; j < i; ++j) {
        if (nums[j] < nums[i]) {
          dp[i] = max(dp[i], dp[j] + 1);
        }
      }
    }
    return *max_element(dp.begin(), dp.end());
  }
};

// 贪心+二分 时间 O(nlogn)
//流程：设当前已求出的最长上升子序列的长度为 nMaxIndex 初始时为1
// dp[i]表示　i之前求得的最长递增子序列比如dp={0,6,10,18,36,37,56,58,73,91},dp[0]不使用
//从前往后遍历数组 nums，在遍历到 nums[i] 时：
//如果 nums[i]>dp[nMaxIndex],则直接加入到dp数组末尾，并更新 nMaxLen=nMaxLen+1
//否则，在 dp 数组中二分查找，找到第一个比 nums[i] 小的数
// dp[k],并更新dp[k+1]=nums[i]

class Solution {  // _greedy
 public:
  int lengthOfLIS(vector<int> nums) {
    if (nums.size() == 0) {
      return 0;
    }
    vector<int> dp(nums.size() + 1, 0);
    size_t nMaxIndex = 1;
    dp[nMaxIndex] = nums[0];
    PF("dp==    %d,%d\n", nMaxIndex, dp[nMaxIndex]);
    for (size_t i = 1; i < nums.size(); i++) {
      PF("n  =  %d\n", nums[i]);
      if (nums[i] > dp[nMaxIndex]) {
        dp[++nMaxIndex] = nums[i];
        PF("dp+    %d,%d\n", nMaxIndex, dp[nMaxIndex]);
        continue;
      }
      // 找不到说明所有的数都比 nums[i] 大此时要更新dp[1]将 pos 设为 0
      size_t iLeft = 1, iRight = nMaxIndex, pos = 0;
      while (iLeft <= iRight) {
        size_t mid = (iLeft + iRight) / 2;
        if (dp[mid] < nums[i]) {
          pos = mid;
          iLeft = mid + 1;
        } else {
          iRight = mid - 1;
        }
      }
      dp[pos + 1] = nums[i];
      PF("dp# %d,%d\n", pos + 1, dp[pos + 1]);
    }
    for (auto n : dp) PF("%d, ", n);
    PF("\n");
    return nMaxIndex;
  }
};
